Міністерство освіти і науки України Тернопільський національний технічний університет імені Івана Пулюя Кафедра комп’ютерних наук Контрольна робота 6 з дисципліни “Теорія алгоритмів” Чи можна побудувати алгоритм знаходження найбільшого спільного дільника двох цілих чисел командами машини Поста? Постом запропоновано алгоритмічну систему у якій дані у пам’яті подаються одним з символів алфавіту А={0,1}. Відомо, що машина Поста виконує всі відомі алгоритми, хоч вона є досить простою. Система команд містить такі команди: перейти до комірки зліва і виконати і-у команду; перейти до комірки справа і виконати і-у команду; записати в комірку 1 і перейти на і-у команду; записати в комірку 0 і перейти на і-у команду; якщо в комірці 1, то перейти до виконання j-ї команди, якщо в комірці 0, то перейти до виконання і-ої команди; зупинка. За допомогою цих команд можна побудувати даний алгоритм. Чи можна побудувати алгоритм командами машини Тьюрінга? Розглянемо склад машини Тюрінга, а саме: пам'ять, що представлена у вигляді нескінченного ланцюжка комірок на один символ; пристрій читання вмісту чарунки; пристрій управління з скінченим числом станів. Тому можна зробити висновок, що алгоритм можна побудувати командами цієї машини. Але на практиці зробити це буде дуже важко. Побудувати алгоритм еквівалентний до алгоритму роботи елементарної системи керування. Два алгоритми є еквівалентними , якщо не співпадають їх оператори, але співпадають області визначення та значень. Отже, за вище розглянутими даними побудуємо еквівалентний алгоритм до алгоритму роботи елементарної системи керування. Беручи до уваги алгоритм її роботи, а також функцію керування, запишемо: множення операндів; додавання операндів; ввести у комірку значення сигналу від керованого об’єкту; вивести значення вихідного сигналу на пристрій виводу; зупинити. Довести еквівалентність трансверсального та рекурсивного алгоритмів. Структурна схема трансверсального алгоритма наступна:
З даної схеми видно, що трансверсальний фільтр виконує сумування попередніх значень вхідного сигналу. Структурна схема трансверсального алгоритма наступна:
Верхня частина структурної схеми відповідає трансверсальному алгоритму. Нижня частина відповідає рекурсивній частині. Якщо порівняти дані структурні схеми, то видно, що область визначення і область значень співпадають, але не співпадають їх оператори. А отже можна судити про те, що вони еквівалентні. Побудувати алгоритм, еквівалентний до алгоритму знаходження найбільшого спільного дільника двох цілих чисел. Ввести більше число у (комірку) х2. Ввести менше число у (комірку) х1. Перемістити вміст комірки x1 в x0. Функція — остача q2 частки від ділення вмісту комірок x2/x0 та остача q1 частки від ділення вмісту комірок x1/x0. Перевірити умову q1 = 0 & q2 = 0. Якщо “Ні”, то перейти до 6 кроку , якщо “Так”, то перейти до 7 кроку. Функція — зменшення вмісту комірки x0 на одиницю і перейти до 4 кроку. Вивести вміст комірки x0. Зупинити. Побудувати алгоритм, еквівалентний до рекурсивного алгоритму розв'язування диференціяльного рівняння другого порядку. Оскільки розв’язок звичайного диференціального рівняння обчислюється за формулою згортки, то еквівалентним алгоритмом може бути числовий алгоритм побудований за рекурсивною формулою